#include "DefineConfiguration.h"
#include "LibraryInterface.h"
#include "BooleanFunction.h"

#include <vector>
#include <initializer_list>
#include <iostream>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <cstdlib>
#include <math.h>
#include "rstream.h"
#include <sstream>


#include "NLLibrary.h"


#define debug

#ifdef debug
#define debug_m(msg) std::cout << msg << std::endl;
#define debug_mp(msg) std::cout << msg; std::cin.get();
#else
#define debug_p(msg) 
#define debug_mp(msg)
#endif

template <typename LIBINFO>
class AttributeMaskNS {
public:
    static UInt64 get(size_t i) {
        static AttributeMaskNS ins;
        return ins.a[i];
    }
private:
    AttributeMaskNS();
    UInt64 a[LIBINFO::n];    
};
template <> AttributeMaskNS<LibraryInfo<2> >::AttributeMaskNS() {
    a[0] = AttributeMask<LibraryInfo<2>,0>::value;
    a[1] = AttributeMask<LibraryInfo<2>,1>::value;
}

template <> AttributeMaskNS<LibraryInfo<3> >::AttributeMaskNS() {
    a[0] = AttributeMask<LibraryInfo<3>,0>::value;
    a[1] = AttributeMask<LibraryInfo<3>,1>::value;
    a[2] = AttributeMask<LibraryInfo<3>,2>::value;
}

template <> AttributeMaskNS<LibraryInfo<4> >::AttributeMaskNS() {
    a[0] = AttributeMask<LibraryInfo<4>,0>::value;
    a[1] = AttributeMask<LibraryInfo<4>,1>::value;
    a[2] = AttributeMask<LibraryInfo<4>,2>::value;
    a[3] = AttributeMask<LibraryInfo<4>,3>::value;
}

template <> AttributeMaskNS<LibraryInfo<5> >::AttributeMaskNS() {
    a[0] = AttributeMask<LibraryInfo<5>,0>::value;
    a[1] = AttributeMask<LibraryInfo<5>,1>::value;
    a[2] = AttributeMask<LibraryInfo<5>,2>::value;
    a[3] = AttributeMask<LibraryInfo<5>,3>::value;
    a[4] = AttributeMask<LibraryInfo<5>,4>::value;
}

template <typename LIBINFO>
class PNFCompCount {
public:
    static const UInt64 sums_count = PNFCompCount<LibraryInfo<LIBINFO::n - 1> >::sums_count * 3;
};

template <> class PNFCompCount<LibraryInfo<1> > {
public:
    static const UInt64 sums_count = 3;
};

template <typename LIBINFO>
class BooleanFunctionSystem {
private:
    std::vector<BooleanFunction<LIBINFO> > funcs;
    
    void add(UInt64 f) {
        funcs.push_back(BooleanFunction<LIBINFO>(f));
    }
public:
    std::vector<UInt64> funcsv;
    std::vector<std::string> funcsvs;
    
    NLLibrary<LIBINFO> lib;
    
    size_t size() const {
        return funcs.size();
    }
    UInt64 operator[] (size_t i) const {
        return funcs[i].f;
    }   
    BooleanFunctionSystem() { }
    
    void createFuncsByV() {
        funcsv.resize(PNFCompCount<LIBINFO>::sums_count);
        funcsvs.resize(PNFCompCount<LIBINFO>::sums_count);
        for(size_t i = 0; i < funcsv.size(); i++) {
            size_t t = i;
            funcsv[i] = filled_mask<LIBINFO::aC>::value;
            
             
            funcsvs[i].resize(LIBINFO::n, 'd');
            
            size_t vi = 0;
            while(t > 0) {
                switch (t % 3) {
                    case 0: break;
                    case 1:
                        funcsvs[i][vi] = 'e';
                        funcsv[i] &= AttributeMaskNS<LIBINFO>::get(vi);
                        break;
                    case 2:
                        funcsvs[i][vi] = 'p';
                        funcsv[i] &= ~AttributeMaskNS<LIBINFO>::get(vi);
                        break;
                }
                t /= 3;
                vi++;
            }
        }
    }
    
    BooleanFunctionSystem(std::initializer_list<UInt64> c) {
        for(std::initializer_list<UInt64>::iterator i = c.begin(); i != c.end(); i++) {
            this->add(*i);
        }
        createFuncsByV();
    }
    
    BooleanFunctionSystem(std::initializer_list<const char*> c) {
        for(std::initializer_list<const char*>::const_iterator i = c.begin(); i != c.end(); i++) {
            std::string str = *i;
            UInt64 f = 0, s = 0;
            for(size_t j = 0; j < str.size(); j++) 
                if (str[j] == '0' || str[j] == '1')
                    f ^= (static_cast<UInt64>(str[j] - '0')) << (j - s);
                else s++;
            this->add(f);
        }
        createFuncsByV();
    }
};

template <typename LIBINFO>
class MinimizatorBFS {
private:
    BooleanFunctionSystem<LIBINFO> &bfs;
public:
    typedef std::set<int> line_type;
    class individual {
    private:
        std::vector<line_type> data;
        int comp;
    public:
        static std::string toString(const BooleanFunctionSystem<LIBINFO> &sys, const line_type::iterator &i) {
            return sys.funcsvs[*i];
        }

        std::string toString(const BooleanFunctionSystem<LIBINFO> &sys, size_t i) const {
            std::string t;
            for(line_type::iterator j = data[i].begin(); j != data[i].end(); j++) {
                line_type::iterator jn = j; jn++;
                t += toString(sys, j);
                if (jn != data[i].end()) t += " ";
            }
            return t;
        }
        
        std::string toString(const BooleanFunctionSystem<LIBINFO> &sys) const {
            std::string t;
            for(size_t i = 0; i < data.size(); i++) {
                t += toString(sys, i) + "\n";
            }
            return t;
        }
        
        int getComp() const {return comp; }
        
        individual(size_t size) {
            comp = 0;
            data.resize(size);
        }
        
        void set(const size_t j, const line_type &a) {
            this->data[j].clear();
            for(line_type::iterator i = a.begin(); i != a.end(); i++) {
                this->data[j].insert(*i);
            }
        }
        
        void switch_item(const size_t i, const int k) {
            line_type::iterator j = data[i].find(k);
            if (j == data[i].end()) 
                data[i].insert(k);
            else 
                data[i].erase(j);
        }            
        
        size_t size(const size_t i) const {
            return data[i].size();
        }
        
        size_t size() const {
            size_t r = 0;
            for(size_t i = 0; i < data.size(); i++) {
                r += size(i);
            }
            return r;
        }
        
        size_t empty_count() const {
            size_t r = 0;
            for(size_t i = 0; i < data.size(); i++) {
                r += size(i) > 0 ? 0 : 1;
            }
            return r;           
        }
        
        int get_random_item(const size_t i) {
            size_t k = randomStream.nextInt();
            if (data[i].size() != 0) {
                k %= data[i].size();
                line_type::iterator j = data[i].begin();
                for(; k--; j++) ;
                if (j != data[i].end()) 
                    return *j;
                return randomStream.nextInt() % PNFCompCount<LIBINFO>::sums_count;
            } else {
                return k % PNFCompCount<LIBINFO>::sums_count;
            }
        }
               
        void update(BooleanFunctionSystem<LIBINFO> &sys) {
            line_type tline;
            UInt8 tcomp;
            comp = 0;
            for(size_t i = 0; i < data.size(); i++) {
                UInt64 f = 0;
                for(line_type::iterator j = data[i].begin();
                        j != data[i].end(); j++) {
                    f ^= sys.funcsv[*j];
                    tline.insert(*j);
                }
                f ^= sys[i];
                sys.lib.get(f, tcomp);
                comp += tcomp;
            }
            comp += tline.size();
        }
        const line_type& at(const size_t i) const {return data[i];}
        
        bool operator < (const individual &a) const {
            if (this->comp < a.comp) return true;
            if (this->comp > a.comp) return false;
            
            for(size_t i = 0; i < a.data.size(); i++) {
                line_type::iterator j1 = this->data[i].begin();
                line_type::iterator j2 = a.data[i].begin();
                for(; j1 != this->data[i].end() && j2 != a.data[i].end(); j1++, j2++) {
                    if (*j1 < *j2) 
                        return true;
                    else if (*j1 > *j2) 
                        return false;
                }
                if (j2 != a.data[i].end()) 
                    return true;
                else if (j1 != this->data[i].end())
                    return false;
            }
            return false;
        }
    };
    
    typedef std::set<individual> Population;
    Population *population;
    
    class SubPopulationCmp {
    public:
        bool operator() (const typename Population::iterator &a, 
                const typename Population::iterator &b) {
            return (const size_t)(&*a) < (const size_t)(&*b);
        }
    };
    typedef std::set<typename Population::iterator, SubPopulationCmp> SubPopulation;
       
    MinimizatorBFS(BooleanFunctionSystem<LIBINFO> &bfs) : bfs(bfs) {
        population = new Population();
    }
    
    void add(individual &a) {
        a.update(this->bfs);
        population->insert(a);
    }
    
    void createStartPopulation() {
        individual a(bfs.size());
        add(a);
        
        line_type tl;
        
        for(size_t i = 0; i < 10; i++) {
            for(size_t j = 0; j < bfs.size(); j++) {
                tl.clear();
                tl.insert(randomStream.nextInt() % bfs.funcsv.size());
                if (randomStream.nextBool())
                    tl.insert(randomStream.nextInt() % bfs.funcsv.size());
                if (randomStream.nextBool()) 
                    tl.insert(randomStream.nextInt() % bfs.funcsv.size());
                a.set(j, tl);
            }
            a.update(bfs);
            add(a);
        }        
    }
    
    void fillSubPopulation(SubPopulation *a, const double p) {
        a->clear();
        size_t s = floor(p * population->size());
        while(a->size() < s) {
            for(typename Population::iterator i = population->begin();
                    i != population->end() && a->size() < s ; i++) {
                if (randomStream.nextBool() || p == 1.0)
                    a->insert(i);
            }
        }
    }
      
    void addCrossovers(const individual &a, const individual &b) {
        individual item1(bfs.size());
        individual item2(bfs.size());
        for(size_t i = 0; i < bfs.size(); i++) {
            if (randomStream.nextBool()) {
                item1.set(i, a.at(i));
                item2.set(i, b.at(i));
            } else {
                item1.set(i, b.at(i));
                item2.set(i, a.at(i));               
            }
        }
        add(item1);
        add(item2);
    }
    
    void addMutations(const individual &a) {
        enum {
            switchItemsNumber = 10,
            selfCrossovers = LIBINFO::n
        };
        
        for(size_t i = 0; i < switchItemsNumber; i++) {
            individual item = a;
            
            item.switch_item(randomStream.nextInt() % bfs.size(), 
                    randomStream.nextInt() % PNFCompCount<LIBINFO>::sums_count);
            
            add(item);
        }
        
        for(size_t i = 0; i < selfCrossovers; i++) {
            individual item = a;
            
            size_t j = randomStream.nextInt() % bfs.size(), j2;
            while( (j2 = randomStream.nextInt() % bfs.size()) == j ) ;
                    
            item.switch_item(j2, item.get_random_item(j));
            
            add(item);
        }

    }
            
            
    void makeReduction(){
        enum {
            bestSolutionNum = 10,
            randomSolutionNum = 10
        };
        
        Population *populationNew = new Population();
        typename Population::iterator i = population->begin();
        for(int j = 0; i != population->end() && j < bestSolutionNum; i++) {
            if (i->empty_count() < bfs.size() - 1) {
                populationNew->insert(*i);
                j++;
            }
        }
        for(; populationNew->size() < bestSolutionNum + randomSolutionNum 
                && i != population->end(); i++) {
            if (randomStream.nextBool())
                populationNew->insert(*i);
        }        
        std::swap(population, populationNew);
        delete populationNew;        
    }

    
    void exec() {
        SubPopulation *cp1 = new SubPopulation(), 
                *cp2 = new SubPopulation(), 
                *mp = new SubPopulation();

        createStartPopulation();

        for(size_t iter = 0; iter < 100; iter++) {
            std::cout << "Iteration " << (iter + 1) << std::endl;
            fillSubPopulation(cp1, 0.5);
            fillSubPopulation(cp2, 0.5);
            fillSubPopulation(mp, 1.0);
            
            for(typename SubPopulation::iterator i = cp1->begin();
                    i != cp1->end(); i++) {
                for(typename SubPopulation::iterator j = cp2->begin();
                        j != cp2->end(); j++) {
                    addCrossovers(**i, **j);                
                }

            }

            for(typename SubPopulation::iterator i = mp->begin();
                    i != mp->end(); i++) {
                addMutations(**i);
            }            
           
            makeReduction();

        } 
            for(typename Population::iterator i = population->begin();
                    i != population->end(); i++) {
                std::cout << i->getComp() << ' ' << i->toString(bfs) << std::endl;
            }


    }
};

int main(int argc, char** argv) {
    BooleanFunctionSystem<LibraryInfo<5> > a({
        "11011011011011011011011011011010",
        "11011011011011011011011011011011"
    });
    std::ostringstream filename;
    filename << LIBRARYDIRECTORIES << "/nllibs/nllibrary_5.bin";
    a.lib.load(filename.str());

        
    MinimizatorBFS<LibraryInfo<5> > mbfs(a);
    std::cout << "Minimization" << std::endl;
    mbfs.exec();
    std::cout << "Finished" << std::endl;
    return 0;
}
